1. Field of the Invention
The present invention relates to the field of multimedia works, and more specifically to a method and apparatus for improving delivery and playback of interactive multimedia works.
2. Background Art
Multimedia works are works containing more than one xe2x80x9cmediaxe2x80x9d such as text, sound, video, still and animated graphics, etc. Multimedia works may be delivered to a viewer (user) in a variety of forms, including live presentations, television broadcasts, computer programs, and Internet web pages. The present invention involves multimedia works that are presented to a user by a delivery device such as a computer, a television, or a similar appliance.
xe2x80x9cInteractivexe2x80x9d multimedia works are multimedia works in which the sequence in which the work is presented is determined by user actions. Examples of interactive multimedia works include computer games, computer based information resource applications (for example a CD-ROM based travel guide or multimedia encyclopedia), websites on the Internet, computer learning programs (for example foreign language programs or college entrance examination study programs), annotated books (for example multimedia versions of classic literary, historical and religious works), interactive television programs, and other works that respond to user input.
The content of an interactive multimedia work can be thought of as a series of individual segments, each having a beginning point and an end point. The individual segments are linked together sequentially in an order determined by the user. Once started, a segment normally executes from its beginning to its end. At the end of a segment a succeeding segment is selected, according to user input, from among a generally finite number of alternatives. The identity and number of segments available at each segment end point are set by the author of the multimedia work.
Each segment includes one or more media elements. For example, a segment may include an introductory graphic animation sequence with an accompanying audio track, followed by a video clip, followed by a screen of text. To present (or xe2x80x9cplayxe2x80x9d) a segment, the playback device being used must have available the appropriate resources in the form of the data to be presented and an appropriate playback system for that form of data. For example, if the playback device is a computer, to play a video clip contained in of a segment of a multimedia work, the computer must have available in its internal memory (for example RAM memory) the video data for the video clip as well as the appropriate application program needed to playback the video data. For example, a segment of a multimedia work may contain a video clip for which the video data is stored in MPEG file format on a CD-ROM disk. In order for the computer to display the video dip, the computer""s processor must have access to an MPEG video player (software that allows the display of MPEG video data) as well as to the MPEG video data itself.
If a playback device used for presenting a multimedia work has unlimited internal memory, all data and application code needed to present a multimedia work can be loaded into the playback device""s memory at one time. The playback device always has all resources available for every segment of the multimedia work. A transition from one segment to the next selected segment can therefore be made nearly instantaneously.
In general, however, a playback device has only a limited amount of internal memory available. Because the size of multimedia works are commonly much larger than a playback device""s available internal memory, only a portion of the data and application code of a multimedia work can be stored in the playback device""s internal memory at one time. The remainder of the data and application code needed to playback the multimedia work must be stored in external memory devices (stores) such a hard drive, a CD-ROM, or a network server. Often, a combination of such stores are used.
In order to proceed without delay from one segment to the succeeding segment, the resources required for the succeeding segment must be available to the playback device""s processor, preferably in quickly accessible internal memory, at the end of the currently playing segment. If the resources required for the succeeding segment are not available at such time, execution of the succeeding segment is delayed while the resources are located and retrieved. If the resources are stored on a CD-ROM drive or a server accessed over a communications network, retrieval of the required resources can take a significant amount of time, causing an excessive and undesirable delay in the execution of the succeeding segment.
If the identity of the succeeding segment were known ahead of time, the resources required for the succeeding segment could be pre-loaded into the playback device""s internal memory while the preceding segment is being executed, assuring that they are available when needed. However, for an interactive multimedia title, for each segment, there are a number of possible succeeding segments. The identity of the actual succeeding segment is not known until the end of the currently executing segment is reached, which is the same time at which the resources required for the succeeding segment are needed.
One possible solution is to pre-load resources for all possible succeeding segments while a segment is being executed. However, doing so is often not possible. First, the available internal memory of a playback device is often not sufficient to store the resources required for all possible succeeding segments. Second, even if the size of the available memory is sufficient, the time required to retrieve all required resources for all possible succeeding segments may exceed the execution time of the currently executing segment. Accordingly, it is often impractical to pre-load the resources for all possible succeeding segments.
If it were possible to guess correctly which of the possible succeeding segments will be selected for execution after a currently executing segment 100% of the time, then the resources only for that succeeding segment would have to be pre-loaded. However, it is in general not possible to predict with 100% certainty which succeeding segment will be selected by user input.
In the prior art, attempts have been made to improve the performance of interactive multimedia titles by attempting to identify, for each segment, the most likely succeeding segment of the possible succeeding segments. Such identification may, for example, be done by the author of an interactive multimedia work at the time the multimedia work is being created based on the author""s best guess of what the most likely user selection will be. The resources for the segment identified as the most likely succeeding segment are then pre-loaded while the preceding segment is being executed.
If a user were to always select the segment that the author has designated as the segment to be pre-loaded, then a multimedia playback system utilizing the prior art method of pre-loading the designated most likely succeeding segment could provide an increase in performance over a system that provides no pre-loading. However, it is unlikely that a user will always choose the designated segment. In fact, if a user always did so, there would be no need for any alternative segments. In cases where the user selects a segment other than the pre-loaded segment, the prior art provides no benefit at all: at the end of the preceding segment, execution of the chosen succeeding segment is delayed while the resources needed for the segment are located and retrieved. The result is highly inconsistent performance: performance is good if a user selects the designated succeeding segment, performance is poor if the user selects any of the other available segments.
There remains a need for a multimedia playback system that provides improved performance regardless of which succeeding segment is selected by user action.
The present invention comprises a system for delivering an interactive multimedia work from a storage device, for example a hard disk drive, a CD-ROM or DVD disk drive, a network server, etc. to a playback device, for example a personal computer, in a manner that provides improved performance regardless of the playback sequence selected by a user.
In one embodiment of the present invention, for each segment of an interactive multimedia work, a probability factor is assigned to each possible alternative succeeding segment. The probability factor assigned to a possible succeeding segment represents an estimate of the probability that the segment will be selected for execution upon the completion of the currently executing segment In one embodiment, the probability factors are assigned by the author of the multimedia work. In another embodiment, the probability factors are dynamically updated based on observations of actual use.
In one embodiment of the invention, in addition to assigning a probability factor to each possible succeeding segment for a preceding segment, a retrieval and delivery time cost factor is also assigned to each possible succeeding segment. The retrieval and delivery time cost factor represents an estimate of the time required to retrieve and deliver to the playback device all of the resources required to execute the segment. The size of a retrieval and delivery time cost factor for a segment depends on a variety of factors, for example the size and storage location of the resources required, the speed of the communications channel between the storage device and the playback device, the amount of traffic at the storage device and along the communications channel, and other factors that determine the time required for a resource to be located, retrieved, and delivered to the playback device. In this embodiment, the probability and time cost factor for each possible succeeding segment are combined to produce a relative priority ranking. Resources for the possible succeeding segments are pre-loaded according to the relative priority ranking. As a result, the latency time between the time a segment is selected as a result of user input and the time at which execution of the segment begins is reduced and the performance of a multimedia work improved.
In one embodiment of the invention, in addition to delivering resources in the order of a relative priority ranking, the resources are also stored according to the relative priority ranking, thereby reducing the average seek time needed to find and retrieve resources and further improving playback performance.
In one embodiment of the invention, for each segment of a multimedia work, a probability factor is determined for each other segment of the multimedia work. This probability factor represents an estimate of the probability that a particular one of the other segments will be executed, not necessarily immediately after the segment, but at some point after the segment. This embodiment accordingly looks ahead not only to the immediately succeeding segment, but to one or more subsequent segments as well. In one embodiment, a time cost factor is combined with the probability factor to produce a relative priority ranking, and resources are pre-loaded according to this priority ranking.
In one embodiment of the invention, the time cost factor for each resource is assigned a fixed value. In another embodiment, the time cost factor is recalculated periodically to reflect changes in location and status of resources.